package main

import "fmt"

//两个升序链表的合并
// 2->5->8->10
// 3->4->6->9
// 2->3->4->5->6->8->9->10

type ListNode struct {
	value int
	next *ListNode
}

//创建链表
func CreatList(nums []int)  *ListNode{
	if len(nums) == 0 {
		return nil
	}

	head := &ListNode{value: nums[0]}
	curr := head
	for i:= 1; i<len(nums); i++{
		curr.next = &ListNode{value: nums[i]}
		curr = curr.next
	}
	return head
}

//合并链表
func merge(head1 *ListNode, head2 *ListNode) *ListNode{
	head := &ListNode{}
	curr := head

	for head1 != nil && head2 != nil {
		if head1.value <= head2.value {
			curr.next = head1
			head1 = head1.next
		}else {
			curr.next = head2
			head2 = head2.next
		}
		curr = curr.next
	}

	//处理剩余节点
	if head1 != nil {
		curr.next = head1
	}else {
		curr.next = head2
	}

	return head.next
}

//打印链表
func PrintList(head *ListNode) {
	curr := head

	for curr != nil{
		fmt.Print(curr.value, " ")
		curr = curr.next
	}
	fmt.Println()
}

func main() {
	nums1 := []int{2, 5, 8, 10}
	nums2 := []int{3, 4, 6, 9}
	head1 := CreatList(nums1)
	head2 := CreatList(nums2)

	fmt.Println("合并前的链表:")
	PrintList(head1)
	PrintList(head2)

	head3 := merge(head1, head2)
	fmt.Println("合并后的链表:")
	PrintList(head3)
}


